package priority_queue.leetcode;

import java.util.*;

/**
 * 查找和最小的k对数字
 */
public class Num373 {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        //创建优先级队列其中队列中保存的pairs对象，传入比较器
        Queue<Pairs> queue=new PriorityQueue<>(new Comparator<Pairs>() {
            @Override
            public int compare(Pairs o1, Pairs o2) {
                return (o2.v1+o2.v2)-(o1.v2+o1.v1);
            }
        });
        //遍历两个数组，其中v1来自nums1数组，v2来自nums2数组，在队列中保存最小的k个数对
        for (int i = 0; i < Math.min(nums1.length, k); i++) {
            for (int j = 0; j < Math.min(nums2.length, k) ; j++) {
                if(queue.size()<k){
                    queue.offer(new Pairs(nums1[i],nums2[j] ));
                }else{
                    int add=nums1[i]+nums2[j];
                    Pairs pairs=queue.peek();
                    if (add<(pairs.v1)+ pairs.v2){
                        queue.poll();
                        queue.offer(new Pairs(nums1[i],nums2[j] ));
                    }
                }
            }
        }
        //此时队列中已经保存了前k个和最小的pairs对象，现在只需要取出v1和v2的值即可
        List<List<Integer>> ret=new ArrayList<>();
        while (!queue.isEmpty()){
            List<Integer> temp=new ArrayList<>();
            Pairs pairs=queue.poll();
            temp.add(pairs.v1);
            temp.add(pairs.v2);
            ret.add(temp);
        }
        return ret;
    }

}


class Pairs  {
    //第一个数组nums的元素
    int v1;
    //第二个数组nums的元素
    int v2;

    public Pairs(int v1, int v2) {
        this.v1 = v1;
        this.v2 = v2;
    }

}